{\magonebf 3.8 Sets  (set)}

An instance $S$ of the data type $set$ is a collection of elements of a 
linearly ordered type $U$, called the element type of $S$. The size of 
$S$ is the number of elements in $S$, a set of size zero is called the 
empty set.


\bigskip
{\bf 1. Declaration of a set type}

\decl set U 

introduces a new data type with name \name\ consisting of all sets with
element type $U$. \precond $U$ is linearly ordered.



\bigskip
{\bf 2. Creation of a set}


\create S {} 

creates an instance \var\ of type \name\ and initializes it to the empty set.

\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
\+\op void insert  {U\ x} 
                         {adds $x$ to \var}
\smallskip
\+\op void del     {U\ x} 
                         {deletes $x$ from \var}
\smallskip
\+\op bool member  {U\ x} 
                         {returns true if $x$ in \var, false otherwise}
\smallskip
\+\op U    choose  {}    
                         {returns an element of \var\ (error if \var\ is empty)}
\+\nop                   {\precond{\var\ is not empty}.}
\smallskip
\+\op bool empty   {}    
                         {returns true if \var\ is empty, false otherwise}
\smallskip
\+\op int  size    {}    
                         {returns the size of \var}
\smallskip
\+\op void clear   {}    
                         {makes \var\ the empty set}


\bigskip
{\bf 4. Iteration}


{\bf forall}($x,S$) 
$\{$  ``the elements of $S$ are successively assigned to $x$''  $\}$

\bigskip
{\bf 5. Implementation}

Sets are implemented by red black trees. Operations insert, del, member
take time $O(\log n)$, empty, size take time $O(1)$, and clear takes time 
$O(n)$, where $n$ is the current size of the set.

